{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Wiggle Sort II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #divide-and-conquer #quickselect #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #分治 #快速选择 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: wiggleSort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #摆动排序 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code>，将它重新排列成 <code>nums[0] < nums[1] > nums[2] < nums[3]...</code> 的顺序。</p>\n",
    "\n",
    "<p>你可以假设所有输入数组都可以得到满足题目要求的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,5,1,1,6,4]\n",
    "<strong>输出：</strong>[1,6,1,5,1,4]\n",
    "<strong>解释：</strong>[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,2,2,3,1]\n",
    "<strong>输出：</strong>[2,3,1,3,1,2]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 <= nums[i] <= 5000</code></li>\n",
    "\t<li>题目数据保证，对于给定的输入 <code>nums</code> ，总能产生满足题目要求的结果</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [wiggle-sort-ii](https://leetcode.cn/problems/wiggle-sort-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [wiggle-sort-ii](https://leetcode.cn/problems/wiggle-sort-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,5,1,1,6,4]', '[1,3,2,2,3,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        k = len(nums)//2\n",
    "        nums.sort(reverse = True)\n",
    "        nums[::2], nums[1::2] = nums[k:], nums[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        length = len(nums)\n",
    "        new_nums = [0]*length\n",
    "        nums.sort(reverse = True)\n",
    "        for i in range(1,length,2):\n",
    "            new_nums[i] = nums.pop(0)\n",
    "        for j in range(0,length,2):\n",
    "            new_nums[j] = nums.pop(0)\n",
    "        for i in range(length):\n",
    "            nums.append(new_nums[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #重复元素必然不对多于数组长度的一半或少一半\n",
    "        nums.sort()\n",
    "        if len(nums)%2==0:\n",
    "            mid=len(nums)//2-1\n",
    "        else:\n",
    "            mid=len(nums)//2\n",
    "        nums[::2],nums[1::2]=nums[mid::-1],nums[len(nums)-1:mid:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"        \n",
    "        nums.sort()\n",
    "        half = len(nums[::2])\n",
    "        nums1 = nums[:half]\n",
    "        nums2 = nums[half:]\n",
    "        nums[::2] = nums1[::-1]\n",
    "        nums[1::2] = nums2[::-1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #重复元素必然不对多于数组长度的一半或少一半\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        re=[]\n",
    "        if n%2==0:\n",
    "            x1,x2=n//2-1,n-1\n",
    "            while x1>=0:\n",
    "                re.append(nums[x1])\n",
    "                re.append(nums[x2])\n",
    "                x1-=1\n",
    "                x2-=1\n",
    "        else:\n",
    "            x1,x2=n//2,n-1\n",
    "            while x1:\n",
    "                re.append(nums[x1])\n",
    "                re.append(nums[x2])\n",
    "                \n",
    "                x1-=1\n",
    "                x2-=1\n",
    "            re.append(nums[x1])\n",
    "        nums[:]=re"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \n",
    "        res = sorted(nums)\n",
    "        nlen = len(nums)\n",
    "        for index, i in enumerate(range((nlen+1)//2-1, -1, -1)):\n",
    "            nums[index*2] = res[i]\n",
    "            \n",
    "        for index, i in enumerate(range(nlen-1, (nlen+1)//2-1, -1)):\n",
    "            #print(i,(i-(nlen+1)//2)*2+1)\n",
    "            print(index, res[i])\n",
    "            nums[index*2+1] = res[i]\n",
    "        \n",
    "        #return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        mnums = sorted(nums)\n",
    "        res = []\n",
    "        \n",
    "       \n",
    "        \n",
    "        mid = len(mnums)//2 - 1\n",
    "        right=len(mnums)-1\n",
    "        if len(mnums)%2==1:\n",
    "            res.append(mnums[mid+1])\n",
    "        \n",
    "        for r in range(len(mnums)//2):\n",
    "            if len(mnums)%2==0:\n",
    "                res += [mnums[mid-r], mnums[right-r]]\n",
    "            else:\n",
    "                res += [ mnums[right-r], mnums[mid-r]]\n",
    "         \n",
    "        nums[:] = res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) <= 2:\n",
    "            nums[:] = sorted(nums)[:]        \n",
    "        #先给nums排序，取中点\n",
    "        #i从mid到0， j从最后到mid+1\n",
    "        if len(nums) > 2:\n",
    "            nums[:] = sorted(nums)[:]\n",
    "            res = []\n",
    "            mid = int((len(nums)-1)/2)\n",
    "            i = mid\n",
    "            j = len(nums)-1\n",
    "            while i >= 0 and j > mid:\n",
    "                res.append(nums[i])\n",
    "                res.append(nums[j])\n",
    "                i-=1\n",
    "                j-=1\n",
    "            if i >= 0:\n",
    "                res.append(nums[i])\n",
    "            nums[:] = res[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "\n",
    "        p, r, q = 0, n - 1, n // 2 + 1\n",
    "        while p < r:\n",
    "            rnd = random.randint(p, r)\n",
    "            nums[rnd], nums[r] = nums[r], nums[rnd]\n",
    "            i = p\n",
    "            for j in range(p, r):\n",
    "                if nums[j] <= nums[r]:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "                    i += 1\n",
    "            nums[r], nums[i] = nums[i], nums[r]\n",
    "            if i - p + 1 == q:\n",
    "                break\n",
    "            elif i - p + 1 > q:\n",
    "                r = i - 1\n",
    "            else:\n",
    "                q -= i - p + 1\n",
    "                p = i + 1\n",
    "\n",
    "        # print(nums[:n//2], nums[n//2], nums[n//2+1:])\n",
    "\n",
    "        center = nums[n // 2]\n",
    "\n",
    "        mapping = list(range(1, n, 2)) + list(range(0, n, 2))\n",
    "\n",
    "        # print(mapping)\n",
    "\n",
    "        i, j, k = 0, 0, n - 1\n",
    "        while j <= k: # why have to cross?\n",
    "            if nums[mapping[j]] > center:\n",
    "                nums[mapping[i]], nums[mapping[j]] = nums[mapping[j]], nums[mapping[i]]\n",
    "                i, j = i + 1, j + 1\n",
    "            elif nums[mapping[j]] < center:\n",
    "                nums[mapping[j]], nums[mapping[k]] = nums[mapping[k]], nums[mapping[j]]\n",
    "                k -= 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: void Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        snums = sorted(nums)\n",
    "        numslen = len(nums)\n",
    "        for  i in  list(range(1,numslen,2)) + list(range(0,numslen,2)) :\n",
    "            nums[i] =snums.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: 'List[int]') -> 'None':\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if not nums or len(nums) == 1:\n",
    "            return\n",
    "        nums.sort()\n",
    "        i, j = 1, math.ceil(len(nums)/2)\n",
    "        nums[:j] = nums[:j][::-1]\n",
    "        nums[j:] = nums[j:][::-1]\n",
    "        while i < len(nums) and j < len(nums):\n",
    "            num = nums[j]\n",
    "            del nums[j]\n",
    "            nums.insert(i, num)\n",
    "            i += 2\n",
    "            j += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort(reverse = True)\n",
    "        mid = len(nums) // 2\n",
    "        nums[1::2],nums[0::2] = nums[:mid],nums[mid:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #本题困难之处在于对于存在相同元素的时候插入问题\n",
    "        #采用三路划分的方法可以将相同元素划分出来，这样反序穿插就可以避免重复元素相邻插入\n",
    "        n = len(nums)\n",
    "        if n < 2:return nums\n",
    "        mid = (0 + n-1) // 2 # 中位数索引\n",
    "        \n",
    "\n",
    "        # 快速排序中的一次划分\n",
    "        def partition(begin,end):\n",
    "            left,right = begin,end\n",
    "            while left < right:\n",
    "                while left < right and nums[left] < nums[right]:right -= 1\n",
    "                if left < right:\n",
    "                    nums[left],nums[right] = nums[right],nums[left]\n",
    "                    left += 1\n",
    "                while left < right and nums[left] < nums[right]: left += 1\n",
    "                if left < right:\n",
    "                    nums[left],nums[right] = nums[right],nums[left]\n",
    "                    right -= 1\n",
    "            return left\n",
    "\n",
    "        # 找到中位数对应的数值\n",
    "        left,right = 0, n-1\n",
    "        while True:\n",
    "            pivot = partition(left,right)\n",
    "            if pivot == mid:break\n",
    "            elif pivot > mid:right = pivot - 1\n",
    "            else:left = pivot + 1\n",
    "\n",
    "        # 三路划分(荷兰旗)\n",
    "        midNum = nums[mid]\n",
    "        left,curr,right = 0, 0, n-1\n",
    "        while curr < right:\n",
    "            if nums[curr] < midNum:\n",
    "                nums[left],nums[curr] = nums[curr],nums[left]\n",
    "                left += 1\n",
    "                curr += 1\n",
    "            elif nums[curr] > midNum:\n",
    "                nums[curr],nums[right] = nums[right],nums[curr]\n",
    "                right -= 1\n",
    "            else:\n",
    "                curr += 1\n",
    "\n",
    "        # 交叉合并\n",
    "        small,big ,_nums = mid,n-1,nums[:]\n",
    "        for i in range(n):\n",
    "            if i%2 == 0:\n",
    "                nums[i] = _nums[small]\n",
    "                small -= 1\n",
    "            else:#big\n",
    "                nums[i] = _nums[big]\n",
    "                big -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# 思路一：先将 nums 降序排序，然后在中间将数组折断，间隔插入\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort(reverse=True)\n",
    "        mid = len(nums) // 2\n",
    "        nums[1::2], nums[::2] = nums[:mid], nums[mid:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# 思路一：先将 nums 降序排序，然后在中间将数组折断，间隔插入\n",
    "# class Solution:\n",
    "#     def wiggleSort(self, nums: List[int]) -> None:\n",
    "#         \"\"\"\n",
    "#         Do not return anything, modify nums in-place instead.\n",
    "#         \"\"\"\n",
    "#         nums.sort(reverse=True)\n",
    "#         mid = len(nums) // 2\n",
    "#         nums[1::2], nums[::2] = nums[:mid], nums[mid:]\n",
    "\n",
    "# 思路二：快速排序 + 荷兰旗【三路划分】 -> 实现 有序数组，然后间隔插入。\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n < 2: return\n",
    "\n",
    "        # 快速排序 中的 一次划分；\n",
    "        # 1、 在数组中选一个基准数（通常为数组第一个）；\n",
    "        # 2、将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边；\n",
    "        # 3、对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。\n",
    "        def partition(begin, end):\n",
    "            left, right = begin, end\n",
    "            while left < right:\n",
    "                while left < right and nums[left] < nums[right]: right -= 1\n",
    "                if left < right:\n",
    "                    nums[left], nums[right] = nums[right], nums[left]\n",
    "                    left += 1\n",
    "                while left < right and nums[left] < nums[right]: left += 1\n",
    "                if left < right:\n",
    "                    nums[left], nums[right] = nums[right], nums[left]\n",
    "                    right -= 1\n",
    "            return left\n",
    "\n",
    "        # 使用 二分法 找到中位数对应的原数组的索引\n",
    "        left, right = 0, n - 1\n",
    "        mid = (0 + n - 1) // 2  # 中位数索引\n",
    "        while True:\n",
    "            tmp = partition(left, right)\n",
    "            if tmp == mid:\n",
    "                break\n",
    "            elif tmp > mid:\n",
    "                right = tmp - 1\n",
    "            else:\n",
    "                left = tmp + 1\n",
    "\n",
    "        # 三路划分【荷兰旗】\n",
    "        # 1、设置三个指针，开始指针begin 目前指向指针current 和末尾指向指针end，假设红，白，蓝分别用0,1,2表示；\n",
    "        # 2、begin和current指针同时指向数组第一个元素，end 指针指向最后一个元素；\n",
    "        # 3、移动current指针，由左向右移动，当遇到数字为0时，将current指向的数字和begin指向的数字交换，并且begin向右移动一位，current也向前移动一位；\n",
    "        # 4、当指向的是1时，继续向后移动一位，元素位置相对不变；\n",
    "        # 5、若current指向的是2时，此时就与end交换元素，然后end向左移动一位，current不变；\n",
    "        # 6、如此循环下去，直到current指向的和end指向的相同时，结束操作！\n",
    "        midNum = nums[mid]\n",
    "        left, cur, right = 0, 0, n - 1\n",
    "        while cur < right:\n",
    "            if nums[cur] < midNum:\n",
    "                nums[left], nums[cur] = nums[cur], nums[left]\n",
    "                left += 1\n",
    "                cur += 1\n",
    "            elif nums[cur] > midNum:\n",
    "                nums[cur], nums[right] = nums[right], nums[cur]\n",
    "                right -= 1\n",
    "            else:\n",
    "                cur += 1\n",
    "\n",
    "        # 交叉合并\n",
    "        small, big, array = mid, n - 1, nums[:]\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = array[small]\n",
    "                small -= 1\n",
    "            else:\n",
    "                nums[i] = array[big]\n",
    "                big -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        p = sorted(nums)\n",
    "        nums.clear()\n",
    "        a, b = n-1, n-(n//2)-1\n",
    "        m = n%2\n",
    "        while b >= 0:\n",
    "            if not b and m:\n",
    "                break\n",
    "            nums.append(p[b])\n",
    "            nums.append(p[a])\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "        if n%2:\n",
    "            nums.append(p[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        mx = max(nums)\n",
    "        mask = 1\n",
    "        cur = nums\n",
    "        while mask <= mx:\n",
    "            buckets = [[] for _ in range(10)]\n",
    "            for x in cur:\n",
    "                i = (x // mask)%10\n",
    "                buckets[i].append(x)\n",
    "            cur = []\n",
    "            for b in buckets:\n",
    "                cur.extend(b)\n",
    "            mask <<= 1\n",
    "        i = (n-1) // 2\n",
    "        for index in range(0,n,2):\n",
    "            nums[index] = cur[i]\n",
    "            i-=1\n",
    "        i = n-1\n",
    "        for index in range(1,n,2):\n",
    "            nums[index] = cur[i]\n",
    "            i-=1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n=len(nums)\n",
    "        buckets=[0]*5001\n",
    "        if n&1 :\n",
    "            s,l=n-1,n-2\n",
    "        else:\n",
    "            s,l=n-2,n-1\n",
    "        for num in nums:\n",
    "            buckets[num]+=1\n",
    "        j=5000\n",
    "        for i in range(1,l+1,2):\n",
    "            while buckets[j]==0:\n",
    "                j-=1\n",
    "            nums[i]=j\n",
    "            buckets[j]-=1\n",
    "        for i in range(0,s+1,2):\n",
    "            while buckets[j]==0:\n",
    "                j-=1\n",
    "            nums[i]=j\n",
    "            buckets[j]-=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        j=(len(nums)+1)//2\n",
    "        if len(nums)%2>0:\n",
    "            mflag=1\n",
    "        else:\n",
    "            mflag=0\n",
    "        while j<len(nums):\n",
    "            if mflag:\n",
    "               i+=1\n",
    "               t=nums[j]\n",
    "               nums.pop(j)\n",
    "               nums.insert(i,t)\n",
    "               i+=1\n",
    "            else:\n",
    "                t = nums[j]\n",
    "                nums.pop(j)\n",
    "                nums.insert(i, t)\n",
    "                i+=2\n",
    "            j += 1\n",
    "        nums.reverse()\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums_copy = [i for i in nums]\n",
    "        nums_copy.sort()\n",
    "\n",
    "        \n",
    "        right = len(nums) - 1\n",
    "        if len(nums) % 2 == 0:\n",
    "            left = int(len(nums) / 2) - 1\n",
    "        else:\n",
    "            left = int(len(nums) // 2)\n",
    "        \n",
    "        flag = 0\n",
    "        for i in range(len(nums)):\n",
    "            if flag == 0:\n",
    "                nums[i] = nums_copy[left]\n",
    "                left = left - 1\n",
    "            else:\n",
    "                nums[i] = nums_copy[right]\n",
    "                right = right - 1\n",
    "            flag = abs(flag - 1)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        arr = sorted(nums)\n",
    "        x = (n + 1) // 2\n",
    "        j, k = x - 1, n - 1\n",
    "        for i in range(0, n, 2):\n",
    "            nums[i] = arr[j]\n",
    "            if i + 1 < n:\n",
    "                nums[i + 1] = arr[k]\n",
    "            j -= 1\n",
    "            k -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def findKthLargest(nums, k):\n",
    "            left, right = 0, len(nums) - 1\n",
    "            while True:\n",
    "                pivot = nums[left]\n",
    "                i, j = left + 1, right\n",
    "                while i <= j:\n",
    "                    if nums[i] < pivot and nums[j] > pivot:\n",
    "                        nums[i], nums[j] = nums[j], nums[i]\n",
    "                        i += 1\n",
    "                        j -= 1\n",
    "                    elif nums[i] >= pivot:\n",
    "                        i += 1\n",
    "                    elif nums[j] <= pivot:\n",
    "                        j -= 1\n",
    "                nums[left], nums[j] = nums[j], nums[left]\n",
    "                if j == k - 1:\n",
    "                    return nums[j]\n",
    "                elif j < k - 1:\n",
    "                    left = j + 1\n",
    "                else:\n",
    "                    right = j - 1\n",
    "                    \n",
    "        def index(i, n):\n",
    "            return (2 * i + 1) % (n | 1)\n",
    "        \n",
    "        if not nums:\n",
    "            return\n",
    "        \n",
    "        n = len(nums)\n",
    "        mid = findKthLargest(nums, (n + 1) // 2)\n",
    "        \n",
    "        i, j, k = 0, 0, n - 1\n",
    "        while j <= k:\n",
    "            if nums[index(j, n)] > mid:\n",
    "                nums[index(i, n)], nums[index(j, n)] = nums[index(j, n)], nums[index(i, n)]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            elif nums[index(j, n)] < mid:\n",
    "                nums[index(j, n)], nums[index(k, n)] = nums[index(k, n)], nums[index(j, n)]\n",
    "                k -= 1\n",
    "            else:\n",
    "                j += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        a = sorted(nums)\n",
    "        a = a[::-1]\n",
    "        i, j = 1, 0\n",
    "        while i < len(nums):\n",
    "            nums[i] = a[j]\n",
    "            i = i + 2\n",
    "            j = j + 1\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            nums[i] = a[j]\n",
    "            i = i + 2\n",
    "            j = j + 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        s = len(nums)-len(nums)//2\n",
    "        a = nums[:s][::-1]\n",
    "        b = nums[s:][::-1]\n",
    "        nums.clear()\n",
    "        for i in range(s):\n",
    "            nums.append(a[i])\n",
    "            if i < len(b):\n",
    "                nums.append(b[i])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        length = len(nums)\n",
    "        mid = (length+1)//2\n",
    "        \n",
    "        first = nums[:mid]\n",
    "        last = nums[mid:]\n",
    "\n",
    "        for i in range(length//2):\n",
    "            # print(first,last,i)\n",
    "            nums[2*i] = first[-i-1]\n",
    "            nums[2*i+1] = last[-i-1]\n",
    "        if length%mid!=0:\n",
    "            nums[-1] = first[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) == 1:\n",
    "            return nums\n",
    "        \n",
    "        # 先排序，然后逆序穿插\n",
    "        N,n = len(nums),len(nums) - 1\n",
    "        snums = sorted(nums)\n",
    "        for i in range(1, N, 2):\n",
    "            nums[i] = snums[n]\n",
    "            n -= 1\n",
    "\n",
    "        for i in range(0, N, 2):\n",
    "            nums[i] = snums[n]\n",
    "            n -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        tmp = sorted(nums)\n",
    "        n = len(nums)\n",
    "        i, j, k = (n+1)//2-1, n-1, 0\n",
    "        while k < n:\n",
    "            nums[k] = tmp[i]\n",
    "            k += 1\n",
    "            i -= 1\n",
    "            if k < n:\n",
    "                nums[k] = tmp[j]\n",
    "                k += 1\n",
    "                j -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        s = len(nums)-len(nums)//2\n",
    "        a = nums[:s][::-1]\n",
    "        b = nums[s:][::-1]\n",
    "        nums.clear()\n",
    "        for i in range(s):\n",
    "            nums.append(a[i])\n",
    "            if i < len(b):\n",
    "                nums.append(b[i])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nsize = len(nums)\n",
    "        middle = nsize//2+1 if nsize%2 else nsize//2\n",
    "\n",
    "        def find_median(low, high):\n",
    "            if low>=high: return (low, low)\n",
    "\n",
    "            rd = random.randint(low, high)\n",
    "            nums[rd], nums[low] = nums[low], nums[rd]\n",
    "            pivot = nums[low]\n",
    "            pl, pm, pr = low, low+1, high+1\n",
    "            # ---[low,pl]--(pl,pm)--[pm==pr, high]---\n",
    "            while pm<pr:\n",
    "                while pm<pr and nums[pr-1]>pivot: pr-=1\n",
    "                if nums[pm]<pivot:\n",
    "                    nums[pm], nums[pl+1] = nums[pl+1], nums[pm]\n",
    "                    pl+=1\n",
    "                    pm+=1\n",
    "                elif nums[pm]>pivot:\n",
    "                    nums[pm], nums[pr-1] = nums[pr-1], nums[pm]\n",
    "                    pr-=1\n",
    "                else: #nums[pm]==pivot\n",
    "                    pm+=1\n",
    "            \n",
    "            nums[pl], nums[low] = nums[low], nums[pl]\n",
    "            if pl<middle<pr: return (pl, pr)\n",
    "            elif middle<=pl: return find_median(low,pl-1)\n",
    "            else: return find_median(pr, high)\n",
    "\n",
    "        def wobbly_list(arr, less, larger):\n",
    "            i, j = 0, middle\n",
    "            # flag = middle>less and nums[less]==nums[middle] and (larger-middle)>=(middle-less)\n",
    "            flag = ~nsize%2 and ((larger-middle)>=(middle-less) or (middle-less)==1 or (larger-middle)==1)\n",
    "            if flag:\n",
    "                for k in range(nsize-1, -1, -1):\n",
    "                    # print(k, i, j)\n",
    "                    if flag:\n",
    "                        nums[k] = arr[j]\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        nums[k] = arr[i]\n",
    "                        i+=1\n",
    "                    flag ^= 1\n",
    "            else:\n",
    "                for k in range(nsize):\n",
    "                    if flag:\n",
    "                        nums[k] = arr[j]\n",
    "                        j+=1\n",
    "                    else:\n",
    "                        nums[k] = arr[i]\n",
    "                        i+=1\n",
    "                    flag ^= 1\n",
    "\n",
    "        \n",
    "        less, larger = find_median(0, len(nums)-1)\n",
    "        flag = (larger-middle)>=(middle-less)\n",
    "        arr = nums[:]\n",
    "        print(arr, nsize, less, middle, larger)\n",
    "        wobbly_list(arr, less, larger)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "\n",
    "        k = len(nums) // 2\n",
    "        if len(nums) % 2 == 0:\n",
    "            k -= 1\n",
    "\n",
    "        base = (len(nums) + 1) if len(nums) % 2 == 0 else len(nums)\n",
    "        def loc_map(i):\n",
    "            return (2 * i + 1) % base\n",
    "\n",
    "        \n",
    "        def partition(i0, j0):\n",
    "            i, j = i0, j0\n",
    "            mid = i0\n",
    "            temp = nums[loc_map(mid)]\n",
    "            while mid <= j:\n",
    "                if nums[loc_map(mid)] == temp:\n",
    "                    mid += 1\n",
    "                elif nums[loc_map(mid)] > temp:\n",
    "                    nums[loc_map(mid)], nums[loc_map(i)] = nums[loc_map(i)], nums[loc_map(mid)]\n",
    "                    i += 1\n",
    "                    if mid < i:\n",
    "                        mid += 1\n",
    "                else:\n",
    "                    nums[loc_map(mid)], nums[loc_map(j)] = nums[loc_map(j)], nums[loc_map(mid)]\n",
    "                    j -= 1\n",
    "\n",
    "            rj = j\n",
    "            ri = j\n",
    "            while ri - 1 >= i0 and nums[loc_map(ri-1)] == nums[loc_map(rj)]:\n",
    "                ri -= 1\n",
    "\n",
    "            return ri, rj\n",
    "\n",
    "        def helper(i0, j0):\n",
    "            # print('a', i0, j0, nums)\n",
    "            i, j = partition(i0, j0)\n",
    "            # print('b', i0, j0, nums)\n",
    "            if i <= k <= j:\n",
    "                return \n",
    "            elif k < i:\n",
    "                helper(i0, i-1)\n",
    "            else:\n",
    "                helper(j+1, j0)\n",
    "\n",
    "        helper(0, len(nums)-1)\n",
    "\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        a = nums[:(n + 1)//2]\n",
    "        b = nums[n//2:]\n",
    "        a = a[::-1]\n",
    "        b = b[::-1]\n",
    "        for i in range(n // 2):\n",
    "            res.append(a[i])\n",
    "            res.append(b[i])\n",
    "        if n & 1:\n",
    "            res.append(a[-1])\n",
    "        nums[:] = res[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def quickSortIn3Way(nums: List[int], l: int, r: int):\n",
    "            if l >= r:\n",
    "                return\n",
    "\n",
    "            pivot = nums[l]\n",
    "            lt, i, gt = l, l + 1, r + 1\n",
    "\n",
    "            while i < gt:\n",
    "                if nums[i] < pivot:\n",
    "                    lt += 1\n",
    "                    nums[lt], nums[i] = nums[i], nums[lt]\n",
    "                    i += 1\n",
    "                elif nums[i] > pivot:\n",
    "                    gt -= 1\n",
    "                    nums[gt], nums[i] = nums[i], nums[gt]\n",
    "                else:\n",
    "                    i += 1\n",
    "\n",
    "            nums[l], nums[lt] = nums[lt], nums[l]\n",
    "\n",
    "            quickSortIn3Way(nums, l, lt - 1)\n",
    "            quickSortIn3Way(nums, gt, r)\n",
    "\n",
    "            \n",
    "        quickSortIn3Way(nums, 0, len(nums) - 1)\n",
    "        \n",
    "        temp = nums[:]\n",
    "        n = len(nums)\n",
    "        r = n - 1\n",
    "\n",
    "        for i in range(1, n, 2):\n",
    "            nums[i] = temp[r]\n",
    "            r -= 1\n",
    "\n",
    "        for i in range(0, n, 2):\n",
    "            nums[i] = temp[r]\n",
    "            r -= 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        mid = (n + 1) // 2 - 1\n",
    "        alist = nums\n",
    "        def partition(left, right):\n",
    "            rand_idx = randint(left, right)\n",
    "            alist[rand_idx], alist[left] = alist[left], alist[rand_idx]\n",
    "            target = alist[left]\n",
    "            init = left\n",
    "            left += 1\n",
    "            while left <= right:\n",
    "                while left <= right and alist[left] <= target:\n",
    "                    left += 1\n",
    "                while left <= right and alist[right] >= target:\n",
    "                    right -= 1\n",
    "                if left <= right:\n",
    "                    alist[left], alist[right] = alist[right], alist[left]\n",
    "            \n",
    "            alist[init], alist[right] = alist[right], alist[init]\n",
    "            return right\n",
    "        \n",
    "        def qucikselect(left, right):\n",
    "            if left < right:\n",
    "                split = partition(left, right)\n",
    "                if split == mid:\n",
    "                    return #alist[split]\n",
    "                elif split < mid:\n",
    "                    qucikselect(split+1, right)\n",
    "                else:\n",
    "                    qucikselect(left, split-1)\n",
    "        \n",
    "        qucikselect(0, n-1)\n",
    "        target = alist[mid]\n",
    "        # print(target, alist)\n",
    "        k, i, j = 0, 0, n - 1\n",
    "        while k <= j:\n",
    "            if alist[k] > target:\n",
    "                while j > k and alist[j] > target:\n",
    "                    j -= 1\n",
    "                alist[k], alist[j] = alist[j], alist[k]\n",
    "                j -= 1\n",
    "            if alist[k] < target:\n",
    "                alist[k], alist[i] = alist[i], alist[k]\n",
    "                i += 1\n",
    "            k += 1\n",
    "        # print(alist)\n",
    "\n",
    "        ans = []\n",
    "        # if n % 2 == 1:\n",
    "        #     mid = mid + 1\n",
    "        i, j = mid, n-1\n",
    "        while (i > -1) or j >= mid+1:\n",
    "            ans.append(alist[i])\n",
    "            if j >= mid+1:\n",
    "                ans.append(alist[j])\n",
    "                # print(ans)\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "        nums[:] = ans[:]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n <= 1: return nums\n",
    "        k = (n + 1) // 2 - 1\n",
    "        mid_value = partition(nums, k, 0, n - 1)\n",
    "        three_way_partition(nums, mid_value)\n",
    "        nums0 = nums.copy()\n",
    "        for k in range(n):\n",
    "            nums[k] = nums0[(n + 1) // 2 - 1 - k // 2] if (not k % 2) else nums0[(n - 1) - k // 2]\n",
    "\n",
    "\n",
    "def partition(nums, k, start, end):\n",
    "    key = nums[start]\n",
    "    left, right = start, end\n",
    "    # print('nums={}, start={}, end={}'.format(nums,start,end))\n",
    "    # 循环中的不变量: left<right and nums[right]>=key and nums[left]<=key\n",
    "    while left < right:\n",
    "        while left < right and nums[right] >= key:\n",
    "            right = right - 1\n",
    "        if left < right: nums[left], nums[right] = nums[right], nums[left]\n",
    "        while left < right and nums[left] <= key:\n",
    "            left = left + 1\n",
    "        if left < right: nums[left], nums[right] = nums[right], nums[left]\n",
    "\n",
    "    if left == k:\n",
    "        return nums[left]\n",
    "    elif left > k:\n",
    "        return partition(nums, k, start, left - 1)\n",
    "    else:\n",
    "        return partition(nums, k, left + 1, end)\n",
    "\n",
    "def three_way_partition(nums, value):\n",
    "    n = len(nums)\n",
    "    l, r = 0, n - 1\n",
    "    i = 0\n",
    "    # 不能让i越过r 否则如果nums[l]<=nums[r]<nums[i] 会在下一次中让右侧更大的数字被换到左侧\n",
    "    while i <= r:\n",
    "        if nums[i] < value:\n",
    "            nums[l], nums[i] = nums[i], nums[l]\n",
    "            l += 1\n",
    "            i += 1\n",
    "        elif nums[i] > value:  # 在这种情况下i不要移动 因为交换过来的数字nums[r]可能仍是>value\n",
    "            nums[r], nums[i] = nums[i], nums[r]\n",
    "            r -= 1\n",
    "        else:\n",
    "            i += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def swap(i, j):\n",
    "            nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "        def quickSelect(left, right):\n",
    "            if left >= right: return\n",
    "\n",
    "            pivot = nums[right]\n",
    "            start, mid, end = left, left, right\n",
    "\n",
    "            while mid <= end:\n",
    "                if nums[mid] < pivot:\n",
    "                    swap(mid, start)\n",
    "                    mid += 1\n",
    "                    start += 1\n",
    "                elif nums[mid] > pivot:\n",
    "                    swap(mid, end)\n",
    "                    end -= 1\n",
    "                else:\n",
    "                    mid += 1\n",
    "            \n",
    "            if start <= k <= mid - 1:\n",
    "                return\n",
    "            elif k < start:\n",
    "                quickSelect(left, start-1)\n",
    "            else:\n",
    "                quickSelect(mid, right)\n",
    "        \n",
    "        k = (len(nums) + 1) // 2\n",
    "        quickSelect(0, len(nums)-1)\n",
    "        \n",
    "        A = nums[k-1::-1]\n",
    "        B = nums[:k-1:-1]\n",
    "\n",
    "        for i in range(len(A)):\n",
    "            nums[2*i] = A[i]\n",
    "        \n",
    "        for i in range(len(B)):\n",
    "            nums[2*i+1] = B[i]\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def partition(nums, pivot, l, r):\n",
    "            i, m, j = l, l + 1, r\n",
    "            while m <= j:\n",
    "                if nums[m] < pivot:\n",
    "                    nums[i], nums[m] = nums[m], nums[i]\n",
    "                    i += 1\n",
    "                    m += 1\n",
    "                elif nums[m] > pivot:\n",
    "                    nums[m], nums[j] = nums[j], nums[m]\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    m += 1\n",
    "            return i, j\n",
    "        \n",
    "        def quick_select(nums, l, r, k):\n",
    "            pivot = nums[l]\n",
    "            i, j = partition(nums, pivot, l, r)\n",
    "            if k < i:\n",
    "                return quick_select(nums, l, i - 1, k)\n",
    "            elif k > j:\n",
    "                return quick_select(nums, j + 1, r, k)\n",
    "            else:\n",
    "                return nums[k]\n",
    "        \n",
    "        k = (len(nums) + 1) // 2\n",
    "        k_small = quick_select(nums, 0, len(nums) - 1, k - 1)\n",
    "        partition(nums, k_small, 0, len(nums) - 1)\n",
    "        nums[::2], nums[1::2] = nums[:k][::-1], nums[k:][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def a(left, right):\n",
    "            if left == right:\n",
    "                return l[left]\n",
    "            i, j, pivot = left, right, l[left]\n",
    "            while i <= j:\n",
    "                if l[i] < pivot:\n",
    "                    i += 1\n",
    "                    continue\n",
    "                if l[j] > pivot:\n",
    "                    j -= 1\n",
    "                    continue\n",
    "                l[i], l[j] = l[j], l[i]\n",
    "                i += 1\n",
    "                j -= 1\n",
    "            return a(left, i - 1) if k <= i else a(i, right)\n",
    "\n",
    "\n",
    "        l = nums\n",
    "        n = len(l)\n",
    "        k = n // 2 + 1\n",
    "        median = a(0, n - 1)  # 中位数\n",
    "        i, j, k = 0, 0, n - 1\n",
    "        while j <= k:  # 3-way-partition\n",
    "            if l[j] == median:\n",
    "                j += 1\n",
    "            elif l[j] < median:\n",
    "                l[j], l[i] = l[i], l[j]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                l[j], l[k] = l[k], l[j]\n",
    "                k -= 1\n",
    "        evenStart = (n - 1) // 2  # 偶数位取值的起点（为了使重复值尽量错开，反向取）\n",
    "        oddStart = n - 1\n",
    "        tmp = l[:]\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                l[i] = tmp[evenStart]\n",
    "                evenStart -= 1\n",
    "            else:\n",
    "                l[i] = tmp[oddStart]\n",
    "                oddStart -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        half = (n-1)//2\n",
    "        middle_num = self.quickSelect(nums, half, 0, n-1)\n",
    "        # print(middle_num)\n",
    "        self.three_way_partition(nums, middle_num)\n",
    "        # 0,1,2,3,4\n",
    "        # half = 2\n",
    "        # left = 0,1,2\n",
    "        # right = 3,4\n",
    "        left = nums[:half+1]\n",
    "        right = nums[half+1:]\n",
    "        p = len(left) - 1\n",
    "        q = len(right) - 1\n",
    "        for i in range(n):\n",
    "            if not i & 1:\n",
    "                nums[i] = left[p]\n",
    "                p -= 1\n",
    "            else:\n",
    "                nums[i] = right[q]\n",
    "                q -= 1\n",
    "\n",
    "    def swap(self, nums, a, b):\n",
    "        # print('swap', a, b, nums[a], nums[b])\n",
    "        nums[a], nums[b] = nums[b], nums[a]\n",
    "\n",
    "    def quickSelect(self, nums, mid, left, right):\n",
    "        pivot = nums[left]\n",
    "        i = left\n",
    "        j = right\n",
    "        while i<j:\n",
    "            while i < j and nums[j] >= pivot:\n",
    "                j -= 1\n",
    "            nums[i] = nums[j]\n",
    "            while i < j and nums[i] <= pivot:\n",
    "                i += 1\n",
    "            nums[j] = nums[i]\n",
    "        nums[j] = pivot\n",
    "        if i == mid:\n",
    "            return pivot\n",
    "        elif i > mid:\n",
    "            return self.quickSelect(nums, mid, left, i-1)\n",
    "        else:\n",
    "            return self.quickSelect(nums, mid, i+1, right)\n",
    "    \n",
    "    def three_way_partition(self, nums, pivot):\n",
    "        lt = 0\n",
    "        eq = 0\n",
    "        gt = len(nums) - 1\n",
    "        while eq < gt:\n",
    "            if nums[eq] == pivot:\n",
    "                eq += 1\n",
    "            elif nums[eq] < pivot:\n",
    "                self.swap(nums, eq, lt)\n",
    "                eq += 1\n",
    "                lt += 1\n",
    "            else:\n",
    "                self.swap(nums, eq, gt)\n",
    "                gt -= 1\n",
    "        # print(lt, eq)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def partition(left, right):\n",
    "            p = nums[left]\n",
    "            l, r = left, right\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= p:\n",
    "                    r -= 1\n",
    "                if l < r:\n",
    "                    nums[l] = nums[r]\n",
    "                while l < r and nums[l] <= p:\n",
    "                    l += 1\n",
    "                if l < r:\n",
    "                    nums[r] = nums[l]\n",
    "            nums[l] = p\n",
    "            return l\n",
    "\n",
    "        def quick_select(left, right):\n",
    "            l = partition(left, right)\n",
    "            if l == len(nums) // 2:\n",
    "                return l\n",
    "            if l < len(nums) // 2:\n",
    "                return quick_select(l+1, right)\n",
    "            else:\n",
    "                return quick_select(left, l-1)\n",
    "\n",
    "        length = len(nums)\n",
    "        mid_idx = quick_select(0, length-1)\n",
    "        mid = nums[mid_idx]\n",
    "        i, j, k = 0, 0, length-1\n",
    "        while j < k:\n",
    "            if nums[j] > mid:\n",
    "                nums[j], nums[k] = nums[k], nums[j]\n",
    "                k -= 1\n",
    "            elif nums[j] < mid:\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                j += 1\n",
    "        # 保证前面的数组 >= 后面的\n",
    "        if length % 2:\n",
    "            mid_idx += 1\n",
    "        a = copy.deepcopy(nums[0:mid_idx][::-1])\n",
    "        b = copy.deepcopy(nums[mid_idx:][::-1])\n",
    "\n",
    "        for i in range(len(a)):\n",
    "            nums[2*i] = a[i]\n",
    "            if i < len(b):\n",
    "                nums[2*i+1] = b[i]\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "\n",
    "        def partition(nums: List[int], l: int, r: int):\n",
    "            if l >= r:\n",
    "                return l, r\n",
    "            pivot = nums[r]\n",
    "            lt, gt = l, r\n",
    "            i = l\n",
    "            # [l, lt-1] [lt, gt] [gt+1, r]\n",
    "            while i <= gt:\n",
    "                if nums[i] > pivot:\n",
    "                    nums[i], nums[gt] = nums[gt], nums[i]\n",
    "                    gt -= 1\n",
    "                elif nums[i] < pivot:\n",
    "                    nums[i], nums[lt] = nums[lt], nums[i]\n",
    "                    lt += 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "            # print(\"pivot\", pivot)\n",
    "            # print(l, lt, gt, r)\n",
    "            # print(nums[l : r + 1])\n",
    "            return lt, gt\n",
    "\n",
    "        # https://wiesen.github.io/post/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AC%94%E8%AE%B0/\n",
    "        # https://xyzghio.xyz/QuickSort/\n",
    "        def kthNum(nums: List[int], l: int, r: int, k: int):\n",
    "            lt, gt = partition(nums, l, r)\n",
    "            if lt <= k <= gt:\n",
    "                return\n",
    "            elif k < lt:\n",
    "                kthNum(nums, l, lt - 1, k)\n",
    "            else:\n",
    "                kthNum(nums, gt + 1, r, k)\n",
    "\n",
    "        l, r = 0, len(nums) - 1\n",
    "        m = (l + r) // 2\n",
    "        # print(\"m\", m)\n",
    "        kthNum(nums, l, r, m)\n",
    "        # print(nums)\n",
    "        nums[::2], nums[1::2] = (\n",
    "            nums[: (len(nums) + 1) // 2][::-1],\n",
    "            nums[(len(nums) + 1) // 2 :][::-1],\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        #快速选择\n",
    "        def quickSelect(nums,s,e,k):\n",
    "            l,r = s,e\n",
    "            pivot = nums[s]\n",
    "            while l < r:\n",
    "                while l < r and nums[r] >= pivot:\n",
    "                    r -= 1\n",
    "                if l < r:\n",
    "                    nums[l] = nums[r]\n",
    "                    l += 1\n",
    "                while l < r and nums[l] <= pivot:\n",
    "                    l += 1\n",
    "                if l < r:\n",
    "                    nums[r] = nums[l]\n",
    "                    r -= 1\n",
    "            nums[l] = pivot\n",
    "            if l < k:\n",
    "                quickSelect(nums,l + 1,e,k)\n",
    "            elif l > k:\n",
    "                quickSelect(nums,s,l - 1,k)\n",
    "        \n",
    "\n",
    "        n = len(nums)\n",
    "        mid = (n - 1) // 2\n",
    "        quickSelect(nums,0,n - 1,mid)\n",
    "\n",
    "        #三路划分\n",
    "        left,cur,right = 0,0,n - 1\n",
    "        while cur < right:\n",
    "            if nums[cur] < nums[mid]:#nums[left]不会大于nums[mid]，所以换过来之后不用比较了，cur继续+1\n",
    "                nums[left],nums[cur] = nums[cur],nums[left]\n",
    "                left += 1\n",
    "                cur += 1\n",
    "            elif nums[cur] > nums[mid]:#nums[right]可能大于等于nums[mid]，cur不能动\n",
    "                nums[cur],nums[right] = nums[right],nums[cur]\n",
    "                right -= 1\n",
    "            else:\n",
    "                cur += 1\n",
    "        \n",
    "        #交叉\n",
    "        small,big,_nums = mid,n - 1,nums[:]\n",
    "        for i in range(n):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = _nums[small]\n",
    "                small -= 1\n",
    "            else:\n",
    "                nums[i] = _nums[big]\n",
    "                big -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        def partition(lst, left, right):\n",
    "            pivot_id = random.randint(left, right)\n",
    "            pivot = lst[pivot_id]\n",
    "            lst[pivot_id], lst[right] = lst[right], lst[pivot_id]\n",
    "            i = left - 1\n",
    "            for j in range(left, right):\n",
    "                if lst[j] <= pivot:\n",
    "                    i += 1\n",
    "                    lst[i], lst[j] = lst[j], lst[i]\n",
    "            i += 1\n",
    "            lst[right], lst[i] = lst[i], lst[right]\n",
    "            return i\n",
    "        \n",
    "        def qsort(lst, left, right, k):\n",
    "            if left > right:\n",
    "                return\n",
    "            mid = partition(lst, left, right)\n",
    "            if mid - left + 1 > k:\n",
    "                qsort(lst, left, mid - 1, k)\n",
    "            else:\n",
    "                qsort(lst, mid + 1, right, k - (mid - left + 1))\n",
    "        \n",
    "        mid = (len(nums) - 1) // 2\n",
    "        qsort(nums, 0, len(nums)-1, mid)\n",
    "        target = nums[mid]\n",
    "        i, j, k = -1, 0, len(nums) - 1\n",
    "        while j <= k:\n",
    "            if nums[j] == target:\n",
    "                j += 1\n",
    "            elif nums[j] < target:\n",
    "                i += 1\n",
    "                nums[i], nums[j] = nums[j], nums[i]\n",
    "                j += 1\n",
    "            else:\n",
    "                nums[k], nums[j] = nums[j], nums[k]\n",
    "                k -= 1\n",
    "        j, k = mid, len(nums) - 1\n",
    "        copy = nums[:]\n",
    "        for i in range(len(nums)):\n",
    "            if i % 2 == 0:\n",
    "                nums[i] = copy[j]\n",
    "                j -= 1\n",
    "            else:\n",
    "                nums[i] = copy[k]\n",
    "                k -= 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        target = n // 2\n",
    "        self.quick_select(nums, 0, n - 1, target)\n",
    "\n",
    "        # 3-way-partition\n",
    "        # [0, i)为小于中位数的元素区间,(j, n - 1]为大于中位数的区间\n",
    "        i, j, k = 0, n - 1, 0\n",
    "        while k <= j:\n",
    "            while k <= j and nums[k] > nums[target]:\n",
    "                nums[j], nums[k] = nums[k], nums[j]\n",
    "                j -= 1\n",
    "            if nums[k] < nums[target]:\n",
    "                nums[i], nums[k] = nums[k], nums[i]\n",
    "                i += 1\n",
    "            k += 1\n",
    "        \n",
    "        temp1 = nums[: (n + 1) // 2]\n",
    "        temp2 = nums[(n + 1) // 2: ]\n",
    "        for i in range(len(temp1)):\n",
    "            nums[2 * i] = temp1[len(temp1) - 1 - i]\n",
    "        for i in range(len(temp2)):\n",
    "            nums[2 * i + 1] = temp2[len(temp2) - 1 - i]\n",
    "    \n",
    "    def quick_select(self, nums: List[int], start: int, end: int, target: int):\n",
    "        if start == end:\n",
    "            return \n",
    "        pivot = nums[start]\n",
    "        left, right = start + 1, end\n",
    "        while True:\n",
    "            while left <= right and nums[left] < pivot:\n",
    "                left += 1\n",
    "            while left <= right and nums[right] > pivot:\n",
    "                right -= 1\n",
    "            if left >= right:\n",
    "                break\n",
    "            nums[left], nums[right] = nums[right], nums[left]\n",
    "            left += 1\n",
    "            right -= 1\n",
    "        nums[start], nums[right] = nums[right], nums[start]\n",
    "        \n",
    "        if right == target:\n",
    "            return \n",
    "        elif right < target:\n",
    "            self.quick_select(nums, right + 1, end, target)\n",
    "        else:\n",
    "            self.quick_select(nums, start, right - 1, target)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def wiggleSort(self, nums: List[int]) -> None:\n",
    "        \"\"\"\n",
    "        Do not return anything, modify nums in-place instead.\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        middle = n // 2\n",
    "        self.quickSelect(nums, 0, n - 1, middle)\n",
    "        mid_val = nums[middle]\n",
    "\n",
    "        # 三分数组\n",
    "        smaller, equal, larger = [], [], []\n",
    "        for num in nums:\n",
    "            if num < mid_val:\n",
    "                smaller.append(num)\n",
    "            elif num > mid_val:\n",
    "                larger.append(num)\n",
    "            else:\n",
    "                equal.append(num)\n",
    "\n",
    "        \n",
    "        new_num = smaller + equal + larger\n",
    "        print(new_num)\n",
    "        if len(new_num) % 2 == 1:\n",
    "            left = middle\n",
    "            right = len(new_num)-1\n",
    "            i = 0\n",
    "            while i < len(new_num)-1:\n",
    "                nums[i] = new_num[left] \n",
    "                i += 1\n",
    "                nums[i] = new_num[right]\n",
    "                i += 1\n",
    "                left -= 1\n",
    "                right -= 1\n",
    "                nums[-1] = new_num[0]\n",
    "        else:\n",
    "            left = middle - 1\n",
    "            right = len(new_num) - 1\n",
    "            i = 0\n",
    "            while i < len(new_num):\n",
    "                nums[i] = new_num[left] \n",
    "                i += 1\n",
    "                nums[i] = new_num[right]\n",
    "                i += 1\n",
    "                left -= 1\n",
    "                right -= 1\n",
    "    def quickSelect(self, nums, left, right, k):\n",
    "        if left >= right:\n",
    "            return\n",
    "        pivot = self.partition(nums, left, right)\n",
    "        if pivot == k:\n",
    "            return\n",
    "        elif pivot < k:\n",
    "            self.quickSelect(nums, pivot + 1, right, k)\n",
    "        else:\n",
    "            self.quickSelect(nums, left, pivot - 1, k)\n",
    "\n",
    "    def partition(self, nums, low, high):\n",
    "        pivot = nums[high]\n",
    "        left, right = low, high - 1\n",
    "        while left <= right:\n",
    "            while left <= right and nums[left] <= pivot:\n",
    "                left += 1\n",
    "            while left <= right and nums[right] >= pivot:\n",
    "                right -= 1\n",
    "            if left < right:\n",
    "                nums[left], nums[right] = nums[right], nums[left]\n",
    "        nums[left], nums[high] = nums[high], nums[left]\n",
    "        return left"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
